package com.learn.algorlthm;

/**
 * @classname:
 * @Description: 剪绳子
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-10 17:23
 *
 * 题目描述：
 *  把一根绳子剪成多段，并且使得每段的长度每积最大。
 *  for example,given n = 2, return 1(2=1+1);given n = 10,return 36(10 = 3 + 3 + 4).
 */
public class Learn14 {

    //1 动态规划解法

    public static int inttegerBreak(int n) {
        //每种长度对应的长度乘积最大值
        int[] dp = new int[n+1];
        dp[1] = 1;
        //遍历得出小于n的每种长度的最大乘积值
        for (int i = 2; i <= n; i++) {
            //遍历得出最后一次分割多少每种才最大
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i -j), dp[j] * (i - j)));
            }
        }

        return dp[n];
    }

    //2 贪心解法

    /**
     * 尽可能多剪长度为3的绳子，并且不允许有长度为我的绳子出现，如果出现了，就从已经切好长度为3的绳子中拿出一段与长度为1
     * 的绳子重新组合，把它们切成两段长度为2的绳子.
     * <p>
     * 证明： 当 n>= 5时， 3(n-3) -2(n-2)= n -5 >= 0。因此把长度大于5的绳子切成两段，令其中一段长度为3可以使得两段
     * 的乘积最大
     */
    public static int inttegerBreak_2(int n) {
        if (n <= 2)
            return 1;
        if (n == 3)
            return 2;
        if (n == 4)
            return 4;
        int timesof3 = n/3;
        if ((n - timesof3*3) == 1)
            timesof3--;
        int timesof2 = (n - timesof3*3)/2;

        return (int) (Math.pow(3, timesof3)*Math.pow(2, timesof2));
    }

}
